package leetcode.code074;

public class SearchMatrix extends Solution074 {

	@Override
	public boolean searchMatrix(int[][] matrix, int target) {
		if (matrix == null || matrix.length == 0)
			return false;
		int x = matrix.length;
		int y = matrix[0].length;
		if (target < matrix[0][0] || target > matrix[x - 1][y - 1]) {
			return false;
		}
		int l = 0;
		int r = x - 1;
		while (l <= r) {
			int m = l + ((r - l) >> 1);
			if (target < matrix[m][0]) {
				r = m - 1;
			} else if (target > matrix[m][0]) {
				l = m + 1;
			} else if (target == matrix[m][0]) {
				return true;
			}
		}
		int row = l - 1;
		l = 0;
		r = y - 1;
		while (l <= r) {
			int m = l + ((r - l) >> 1);
			if (target < matrix[row][m]) {
				r = m - 1;
			} else if (target > matrix[row][m]) {
				l = m + 1;
			} else if (target == matrix[row][m]) {
				return true;
			}
		}
		return false;
	}


	public static void main(String[] args) {
		SearchMatrix so = new SearchMatrix();
		so.debug1();
		so.debug2();
	}

}
